pub fn dp_rec_mc(amount: u32) -> u32 {
    let denominations = [1, 2, 5, 10, 20, 30, 50, 100];
    let amount: usize = amount.try_into().unwrap();
    let mut dp = vec![std::usize::MAX; amount + 1]; // 初始化 dp 数组
    let mut coin_used = vec![0; amount + 1];        // 记录用于找零的面额
    dp[0] = 0; // 找零金额为 0 时，所需纸币数为 0

    // 填充 dp 数组
    for i in 1..=amount {
        for &coin in &denominations {
            if i >= coin {
                // 如果使用当前面额纸币能更小，则更新 dp[i] 和 coin_used[i]
                if dp[i - coin] != std::usize::MAX && dp[i - coin] + 1 < dp[i] {
                    dp[i] = dp[i - coin] + 1;
                    coin_used[i] = coin;
                }
            }
        }
    }

    // 如果 dp[amount] 仍是初始值，说明无法找零
    if dp[amount] == std::usize::MAX {
        return 0;
    }

    // 计算最小纸币数和每种纸币的数量
    let mut result: Vec<(u32, i32)> = Vec::new();
    let mut remaining = amount;
    let mut total_coins = 0;

    while remaining > 0 {
        let coin = coin_used[remaining];
        let count = result.iter_mut().find(|x| x.0 == coin as u32);
        match count {
            Some((_, c)) => *c += 1,
            None => result.push((coin as u32, 1)),
        }
        total_coins += 1;
        remaining -= coin;
    }

    println!("Min {} with : {:?}", total_coins, result);
    total_coins
}
